// https://leetcode.cn/problems/path-sum/

// 算法思路总结：
// 1. 深度优先搜索判断路径和是否存在
// 2. 递归遍历所有根到叶子的路径
// 3. 到达叶子节点时检查路径和是否等于目标值
// 4. 使用全局flag标记是否找到满足条件的路径
// 5. 时间复杂度：O(n)，空间复杂度：O(h)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>
#include <string>
#include "BinaryTreeUtils.h"

class Solution 
{
public:
    bool flag;

    bool hasPathSum(TreeNode* root, int targetSum) 
    {
        if (root == nullptr) return false;

        flag = false;
        int path = 0;

        recur(path, targetSum, root);

        return flag;
    }

    void recur(int path, int targetSum, TreeNode* root)
    {
        if (root == nullptr)
        {
            return ;
        }

        path += root->val;
        if (root->left == nullptr && root->right == nullptr)
        {
            if (path == targetSum)
            {
                flag = true;
            }
            return ;
        }

        recur(path, targetSum, root->left);
        recur(path, targetSum, root->right);

        return ;
    }
};

int main()
{
    vector<string> tree1 = {"5","4","8","11","null","13","4","7","2","null","null","null","1"};
    vector<string> tree2 = {"1","2","3"};
    int targetSum1 = 22, targetSum2 = 5; 
    Solution sol;

    auto root1 = buildTree(tree1);
    auto root2 = buildTree(tree2);

    bool flag1 = sol.hasPathSum(root1, targetSum1);
    bool flag2 = sol.hasPathSum(root2, targetSum2);

    cout << (flag1 == true ? "True" : "False") << endl;
    cout << (flag2 == true ? "True" : "False") << endl;

    
    return 0;
}